#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        if (n == 1)
            return findTar(matrix[0], target);

        for (int i = 0; i < n - 1; ++i)
        {
            if (target >= matrix[i][0] && target < matrix[i + 1][0])
            {
                return findTar(matrix[i], target);
            }
        }

        return findTar(matrix[n - 1], target);
    }

    bool findTar(vector<int> mat, int target)
    {
        int n = mat.size();
        int left = 0, right = n - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (mat[mid] > target)
                right = mid - 1;
            else if (mat[mid] < target)
                left = mid + 1;
            else
                return true;
        }
        return false;
    }
};